// https://www.lintcode.com/problem/number-of-islands/

public class Solution {
    /**
     * @param grid: a boolean 2D matrix
     * @return: an integer
     */
    public int numIslands(boolean[][] grid) {
        // write your code here
        if (0 == grid.length) {
            return 0;
        }
        int ret = 0, rows = grid.length, cols = grid[0].length;
        for (int r = 0; r < rows; ++r) {
            for (int c = 0; c < cols; ++c) {
                if (grid[r][c]) {
                    ret += 1;
                    mark(grid, r, c);
                }
            }
        }
        return ret;
    }
    
    private void mark(boolean[][] grid, int row, int col) {
        if (grid[row][col]) {
            grid[row][col] = false;
            if (row > 0) { // 上
                mark(grid, row - 1, col);
            }
            if (row < (grid.length - 1)) {  // 下
                mark(grid, row + 1, col);
            }
            if (col > 0) {  // 左
                mark(grid, row, col - 1);
            }
            if (col < (grid[0].length - 1)) {  // 下
                mark(grid, row, col + 1);
            }
        }
    }
}